The Binary search tree is a data structure consisting of nodes. The nodes are either null or have reference to other (child) nodes. Every node can have up to 2 nodes, called the left node or the right node. Each node will also contain a value, which will determine where these nodes are placed within the BST.
Just like a linked list, each node is referenced by only the other node; which is its parent node. The root node is the only node in the BT or BST which doesn’t have any parent node. The binary search tree is a binary tree data structure with the single property: The left sub-tree of a node has only nodes with a value less than the node’s value. Both the left and right subtrees must also be binary search trees.
C++ Binary Search Tree
void Search(node *root, int data) { int depth = 0; node *temp = new node; temp = root; while(temp != NULL) { depth++; if(temp->data == data) { cout<<"\nElement found at depth: "<<depth; return; } else if(temp->data > data) temp = temp->left; else temp = temp->right; } cout<<"\n Not found"; return; }
How does the program work?
Let’s say, you already have a BST created from an array arr[10] ={4,5,7,2,7,4,6,3,5,7} .
This Binary search tree can be accessed via a node pointer root.
Just call the above function on the root node of the BST. If the number exists in BST, it will return the level/depth. Otherwise, it will display a text message “Not found.”
node *root = new node; Search(root, number_to_be_found);